
// T-408-STNE
// Operating systems and networks
// Spring 2011
// Programming assignment 2: Page replacement algorithms
//
// Implementation of the LruAlgorithm page replacement algorithm.
// Based on code by Olafur R. Helgason

// We implemented the LruAlgorithm algorithm fully using a linked list as mentioned at page
// 204 in Tanenbaum, as opposed to the n x n matrix way which is more system implementation
// friendly

import java.io.*;
import java.util.*;

public class LruAlgorithm
{
	//
	// fifoAlgorithm
	//
	// Class constructor. Also runs the experiment on the page references given in memString
	// The memory is represented as a linked list, ordered by time of reference so the head is the
	// oldest and the tail the most recent. Note that you may need a different memory representation
	// for your algorithms.
	//
	public LruAlgorithm(int memSize, int memString[]) 
	{
		// The usual initialization.
		_pageFaults = 0;
		_memory = new LinkedList();
		_memSize = memSize;
		// Run our experiment
		for (int i = 0; i < memString.length; i++)
			memAccess(memString[i]);
	} 

	//
	// memAccess
	//
	// Access a virtual memory page. We count a page fault if the virtual page is not in 
	// memory.
	//
	private void memAccess(int page) 
	{
		if (!_memory.contains(new Integer(page)))
		{
			//System.out.println("Not in memory: " + page);			
			pageFault(page);
			//printmem();
		}
		else 
	// If the page is in memory
			{
			// Move the page to the back of the list
			//System.out.println("In memory: " + page);			
			_memory.remove(new Integer (page));
			_memory.addLast(new Integer (page));
			//printmem();
			}
	}

	//
	// pageFault
	//
	// Page fault handling. This is the section of code that you shoud change in implementing your
	// other page replacement algorithms
	//
	private void pageFault(int page) 
	{
		_pageFaults++; // Increment the page fault counter.

		// Check if there is space in our memory -- free page frames.
		if (_memSize == _memory.size())
		{
			//System.out.println("Removing: " + _memory.getFirst());
			_memory.removeFirst();
		}
		_memory.addLast(new Integer(page));
	}

	//
	// pageFaults
	//
	// Give the total page faults generated in the experiment
	//
	public int pageFaults() 
	{
		return _pageFaults;
	}
	
	public void printmem() 
	{
		System.out.println(_memory.toString());
	}

	private LinkedList _memory;		// The simulated memory
	private int _memSize;			// Memory size in page frames
	private int _pageFaults;		// Page fault count
}
